#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <stack>
#include <string>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode* ret = nullptr;
    bool findP(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        if (root == nullptr)
            return false;
        bool existL = findP(root->left, p, q);
        bool existR = findP(root->right, p, q);
        if (existL && existR || ((existL || existR) && (root->val == p->val || root->val == q->val)))
        {
            ret = root;
        }
        return existL || existR || root->val == p->val || root->val == q->val;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        findP(root, p, q);
        return ret;
    }
};

int main()
{
	return 0;
}
